﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//1,最简单的想法，归并排序，两两归并
//2，暴力，每次添加一个到结果上面
public class Solution23
{
    public ListNode MergeKLists(ListNode[] lists)//1,最简单的想法，归并排序，两两归并
    {
        int len=lists.Length;
        if (len == 0)
        {
            return null;
        }
        if(len==1) {
            return lists[0]; }


      return   Merge(lists, 0, len - 1);

    }

    private ListNode Merge(ListNode[] lists, int left, int right)
    {

        if (left == right)
        {
            return lists[left];//只有一个链表，直接返回
        }
        int mid=(left+right)/2;


        ListNode leftList= Merge(lists, left,mid );//左边
        ListNode rightList = Merge(lists, mid+1, right );//左边

     return    MergeList(leftList, rightList);

    }

    public ListNode MergeKLists2(ListNode[] lists)
    {
        ListNode res= null;
        for (int i = 0; i < lists.Length; i++)
        {
            res = MergeList(lists[i], res);
        }



        return res;
    }
    public ListNode MergeList(ListNode list1, ListNode list2)//迭代法
    {
        if (list1 == null)
        {
            return list2;
        }
        if (list2 == null)
        {
            return list1;
        }

        ListNode dummyhead = new ListNode(-1);
        ListNode head = dummyhead;
        while (list1 != null&& list2 != null) { 
        
        
        if (list1.val>list2.val) { //挂list2


                head.next = list2;
                
                list2 = list2.next;


            }
            else
            {
                head.next = list1;
                
                list1= list1.next;
            }
            head = head.next;
        }
        if (list1 == null)
        {
            head.next = list2;

        }
        else
        {
            head.next = list1;
        }


        return dummyhead.next;
        }
    }

class Program23
{
    public static ListNode MakeList(int[] nums)
    {
        ListNode dummyhead = new ListNode(-1);
        ListNode head = dummyhead;
        for (int i = 0; i < nums.Length; i++)
        {
            head.next = new ListNode(nums[i]);
            head = head.next;
        }
        return dummyhead.next;


    }
    static void Main23(string[] args)
    {
        //建一个链表数组
        ListNode[] lists = new ListNode[10];
        //一个函数，传入数组，返回链表
        int[] a = { 1, 4, 5 };
        int[] b = { 1, 3,4 };
        int[] c = { 2,6};
        lists[0] = MakeList(a);
        lists[1] = MakeList(b);
        lists[2] = MakeList(c);

        Solution23 solution = new Solution23();
        ListNode res= solution.MergeKLists(lists);
        while(res != null)
        {
            Console.WriteLine(res.val);
            res=res.next;
        }


    }

}

